package baseclass.k_array;

import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 小跟堆实现TopK。时间O(nlogk)，空间O(k)
 *
 * 优势：面对数据流，空间也是O(k)
 * @date 2020/3/4 22:01
 */
public class Code05_TopK_Heap {
    Queue<Integer> minQ;
    final int K;

    public Code05_TopK_Heap(int k) {
        minQ = new PriorityQueue<>();
        K = k;
    }
    public void add(int e){
        if(minQ.size() < K){
            minQ.add(e);
            return;
        }
        if(minQ.peek() < e){
            minQ.poll();
            minQ.add(e);
        }
    }
    public void add(int...arr){
        for (int e : arr) {
            add(e);
        }
    }
    public Integer[] getTopK(){
        return minQ.toArray(new Integer[0]);
    }

    public static void main(String[] args) {
        Code05_TopK_Heap queue = new Code05_TopK_Heap(3);
        int[] arr = {1,-1,5,2,4,342,51,1};
        queue.add(arr);
        for (Integer integer : queue.getTopK()) {
            System.out.println(integer);
        }

    }
}
